#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
//直接插入排序O(N^2)，最好场景O(N)
void InsertSort(int* a, int n)
{							//n是数据个数
	//[0,end]有序，插入tmp依旧有序
	for (int i = 1; i < n; i++)
	{	//i=0是有序的 
		int end = i - 1; 
		int tmp = a[i]; 
		//从后往前比 
		while (end >= 0)//当tmp比所有都小
		{				//end=-1，跳出，同时
						//数组空出了a[0]
			if (a[end] > tmp) 
			{
				a[end + 1] = a[end];
				--end;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
	
}

int main()
{
	;
}